An ad hoc network generally includes a number of mobile devices (or nodes) that typically communicate with each other using some type of wireless signal. The types of wireless signals in use can include, but are not limited to, infrared signals and radio frequency (RF) signals including short wave, Bluetooth, and IEEE 802.11.
By virtue of their mobility, the nodes in an ad hoc network are continually moving into and out of communication range with other nodes. Thus, the topology of such a network is dynamic and temporal, as two nodes in communication range at one point in time may not be in communication range at a later time.
Because of their dynamic nature, searching for and retrieving information residing in the ad hoc network can be problematic. This problem is illustrated by Prior Art FIG. 1.
Prior Art FIG. 1 illustrates an ad hoc network that consists of nodes 2, 3, 6, 7 and 8. As illustrated, nodes 7 and 8 can communicate directly, as can nodes 6 and 7, nodes 3 and 7, nodes 2 and 6, and nodes 2 and 3. In addition, node 8, for example, can communicate indirectly to node 3, for example, via node 7. The other nodes (1, 4, 5, 9, 10 and 11) are not within communication range of any of the nodes 2, 3 6, 7 or 8.
A problem occurs when, for example, node 8 seeks to retrieve information from one of the nodes 2, 3, 6 or 7. Any one of these nodes may move out of communication range at any time, meaning that node 8 would no longer be able to retrieve information from them. Nodes that are more than one “hop” away from node 8 (e.g., nodes 2, 3 or 6) may move in and out of range without node 8 being aware. Thus, a message from node 8 intended for node 2, for example, may or may not reach node 2. If the message from node 8 does indeed reach node 2, then node 2 or node 8 (or one of the intervening nodes 3, 6 or 7) may in the meantime move out of communication range, severing the communication link between nodes 2 and 8 before node 2 can respond. In addition, a unique identifier may not be associated with each node, and so generally it is not possible to send a message (or a response) to a particular node (e.g., node 8), nor to send a response to a query back along the same path that the query traveled.
A similar problem occurs when, for example, node 8 is seeking information that resides only on node 1. In the example of Prior Art FIG. 1, nodes 1 and 8 are not in communication range. Also, none of the nodes in the ad hoc network (e.g., nodes 2, 3, 6 and 7) are able to communicate with node 1, so that a communication path from node 8 to node 1 is not established. However, it is possible that, at some future point in time, a communication path between nodes 1 and 8 may be established, perhaps via one or more hops over intervening nodes. Even so, should node 8 get a message to node 1, it still might not be possible for node 1 to respond to node 8, as explained above. In fact, when separated from node 8 by several hops, node 1 will likely not know that node 8 is the node seeking information, and therefore node 1 will not know where to direct a response.
Therefore, in general, searching for and retrieving information that resides in an ad hoc network is difficult because communication paths between nodes are continually changing. A communication path that was present when a search for an item of information was initiated may not be present by the time the item of information is located. Also, a node that has the sought-for item of information may not know where to send the information. Accordingly, what is needed is a method that can facilitate the search for and retrieval of information residing in an ad hoc network. What is also needed is a method that can satisfy this need without hindering the mobility of the nodes that form the ad hoc network. The present invention provides a novel solution to these needs.